//
// Created by lenovo on 2021/7/2.
//

#include <iostream>

using namespace std;

/**
 * 朴素模式匹配算法(BF)
 * @param s 主串，长度为 n
 * @param t 模式串，长度为 m
 * @return 匹配的话，返回 t 在 s 中第一次出现的位置，不匹配则返回 -1
 * 时间复杂度：O(nm)
 */
int Index(const string& s, const string& t) {

    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s[i] == t[j]) {     // 继续比较后继字符
            i ++;
            j ++;
        } else {                // 指针后退重新开始匹配
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == t.length()) return i - t.length(); // 匹配成功
    return -1;
}

/**
 * 求模式串 t 的 next 数组
 * next 数组的作用：当模式串的第 j 号字符失配时，从模式串的第 next[j] 号字符继续往后匹配
 * next[j] == -1 说明第一个字母就不匹配
 * 时间复杂度：O(m)
 */
void get_next(const string& t, int next[]) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < t.length()) {
        if (j == -1 || t[i] == t[j]) {
            i ++;
            j ++;
            // 若 t[i] = t[j], 则 next[j + 1] = next[j] + 1
            next[i] = j;
        } else  // 否则令 j = next[j]，循环继续
            j = next[j];
    }
}

/**
 * 优化后的 kmp 算法
 * @param t 模式串
 * @param nextval 消除了重复匹配
 */
void get_nextval(const string& t, int nextval[]) {
    // 先算出 next 数组
    int next[t.length()];
    get_next(t, next);
    nextval[0] = -1;
    for (int j = 1 ; j < t.length() ; j ++) {
        // 优化核心
        // 现在的字符跟匹配失败之后的将要匹配的字符相同时，直接将其 nextval 置为将要匹配的字符的 nextval
        if (t[j] == t[next[j]]) nextval[j] = nextval[next[j]];
        // 否则 next 值不变
        else nextval[j] = next[j];
    }
}

/**
 * KMP 匹配算法
 * @param s 主串，长度为 n
 * @param t 模式串，长度为 m
 * @param next
 * @return 匹配成功，返回 t 在 s 中第一次出现的位置；匹配失败，返回 -1
 * 求 next 数组时间复杂度：O(m)
 * 时间复杂度：O(n + m)
 */
int Index_KMP(const string& s, const string& t) {
    int i = 0, j = 0;
    int next[t.length()], nextval[t.length()];
    get_next(t, next);
    get_nextval(t, nextval);
    for (int k = 0; k < t.length(); k++) {
        printf("next[%d]=%d\t\t", k, next[k]);
        printf("nextval[%d]=%d\n", k, nextval[k]);
    }
    // 当无符号数与有符号数比较时，有符号数自动转换为无符号数
    while (i < s.length() && j < (signed)t.length()) {
        if (j == -1 || s[i] == t[j]) {  // j == -1 说明第一个字符就不匹配，主串需要移动
            i ++;                       // 继续比较后继字符
            j ++;
        } else {                        // 模式串向右移动
            j = nextval[j];
        }
    }
    if (j == t.length()) return i - t.length(); // 匹配成功
    return -1;
}


int main() {

    string s = "abaacaabcabaabc", t = "abaabc";
    cout << "s = " << s << endl;
    cout << "t = " << t << endl;
    printf("Index(s, t) = %d\n", Index(s, t)); // 9
//    int next[6] = {-1, 0, 0, 1, 1, 2};
    printf("Index_KMP(s, t) = %d\n\n", Index_KMP(s, t)); // 9

    string ss = "goolggooglexxx", tt = "google";
    cout << "ss = " << ss << endl;
    cout << "tt = " << tt << endl;
    printf("Index(ss, tt) = %d\n", Index(ss, tt)); // 9
    printf("Index_KMP(ss, tt) = %d\n", Index_KMP(ss, tt)); // 9

/*    string s = "123456";
    if (-1 > (signed)s.length()) cout << "大于" << endl;
    else cout << "小于" << endl;*/

    return 0;
}